from tools_algorithm import *


class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        l = 0
        h = Counter()
        ans = 0
        for i, v in enumerate(s):
            h[v] += 1
            while h[v] > 2:
                h[s[l]] -= 1
                l += 1
            ans = max(ans, i - l + 1)

        return ans


class Solution:
    def minOperations(self, k: int) -> int:
        if k <= 1:
            return 0
        a = 1
        t = 0
        ans = inf
        while a < k:
            ans = min(ans, (k - 1) // a + t)
            t += 1
            a += 1

        return ans


class Solution:
    def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
        cnt = Counter()
        q = []
        ans = []
        for num, f in zip(nums, freq):
            cnt[num] += f
            heappush(q, (-cnt[num], num))
            while q and cnt[q[0][1]] != -q[0][0]:
                heappop(q)
            ans.append(-q[0][0] if q else 0)
        return ans


class Node:

    def __init__(self) -> None:
        self.h = {}
        self.i = None


class Solution:
    def stringIndices(
        self, wordsContainer: List[str], wordsQuery: List[str]
    ) -> List[int]:
        n = len(wordsContainer)
        ids = list(range(n))

        def f(i, j):
            if len(wordsContainer[i]) != len(wordsContainer[j]):
                return len(wordsContainer[j]) - len(wordsContainer[i])
            return j - i

        ids.sort(key=cmp_to_key(f))
        root = Node()
        defaulti = 0
        for i in ids:
            word = wordsContainer[i]
            if len(word) < len(wordsContainer[defaulti]) or (
                len(word) == len(wordsContainer[defaulti]) and i < defaulti
            ):
                defaulti = i
            node = root
            for w in word[::-1]:
                if w not in node.h:
                    node.h[w] = Node()
                node = node.h[w]
                node.i = i
        ans = []
        for word in wordsQuery:
            node = root
            for w in word[::-1]:
                if w in node.h:
                    node = node.h[w]
                else:
                    break
            ans.append(defaulti if node.i is None else node.i)

        return ans


s = Solution()
print(
    s.stringIndices(
        wordsContainer=["abcdefgh", "poiuygh", "ghghgh"],
        wordsQuery=["gh", "acbfgh", "acbfegh"],
    )
)  #
print(
    s.stringIndices(
        wordsContainer=["abcd", "bcd", "xbcd"], wordsQuery=["cd", "bcd", "xyz"]
    )
)
